Modern digital text editors and word processors commonly have search utilities for finding user-defined text string and replacement utilities for substituting a user-preferred text string for a target text string wherever the target text is found.
Synthetic graphical images often contain repeated geometric shapes and repeated graphical properties. For example, a digital illustration may have multiple instances of a given color, typeface or line width. Likewise, a certain shape may appear repeatedly in such an illustration, and the different instances of the given shape may be at different translations, rotations and magnifications. As will be appreciated, it may be necessary or desireable to "coherently" change such an illustration, whereby all instances of a repeated shape or property are modified consistently.
Prior digital graphic editors have included clustering and instancing functions for assisting users who wish to make coherent changes to illustrations. Clustering enables a user to collect objects into groups, which commonly are called "clusters," such that the objects of a given cluster can be selected and operated upon as a single unit. Properties of clustered objects, such as their color and their line width and style, can be coherently changed easily and quickly, but clustering does not facilitate changing the shape of the clustered objects. Instancing, on the other hand, permits a user to declare that a selected object is an "instance" of a library object, whereby any change made to the shape or properties of the library object are reflected automatically in all instances of that object. Clustering and instancing, however, are of limited utility. One of their drawbacks is that they require the user to decide in advance which of the objects of an illustration might require coherent editing because the illustration must be structured to cluster or instance those objects. Another of their limitations is that they do not give the user the freedom to decide on a case-by-case basis which objects are and are not to be changed.
Accordingly, it will be evident that there is a need for a graphical search and replace utility. As used herein, "graphical search" refers to a technique for finding all instances of a specified graphical pattern in an arbitrarily structured synthetic graphic image composed of objects which are defined by lines and curves or by regions bounded by lines and curves. "Graphical replace," on the other hand, refers to a technique for replacing selected characteristics (e.g., shape, color, line width, line style, text typeface) of matched objects (i.e., objects responding to a user defined search request) with new characteristics described by a user specified replacement pattern.
The foregoing definitions will suggest still further applications for a graphical search and replace utility. For example, graphical objects can be represented in a database, thereby enabling them to be accessed by queries expressed in traditional database query languages or in new languages specifically designed for formulating graphical object queries. Graphical search and replace may be used as an interface to a graphical database. It not only provides an efficient algorithm for finding curves and groups of curves, but it also permits graphical queries to be expressed simply by drawing or otherwise defining an example of the target object of such a query. Similarly, graphical search and replace may be employed for specifying graphical grammars that generate recursive shapes. Shape grammars (a subset of graphical grammars) have been investigated by others, especially as applied to producing realistic imagery. These shape grammers describe rules for replacing existing shapes with new shapes. Graphical search and replace extends the functionality of such shape grammars because it permits the user to define graphical parameters (e.g., color, line width, line style, text typeface) of the replacement pattern in addition to its shape. Thus, it will be understood that a graphical search and replace technique is a "user-friendly" framework for supporting the creation of recursive shapes, template shapes, and graphical macros.
Others have developed pattern recognition algorithms that could be employed for finding occurences of user-specified geometric shapes in digital images. Some of these algorithms are suitable for carrying out the search phase of a graphical search and replace operation. However, algorithms that are optimized for finding pattern matches in images produced by digital graphics editors are preferred. For example, the algorithm advantageously is optimized for quickly determining whether two curves have the same shape or not by determining whether they are composed of the same ordered set of segments or not. It also desireably is optimized to provide a single pass, deterministic procedure for finding all occurrences of a given graphical search pattern in a predefined synthetic graphics scene, file or database.